/*******************************************************************************
    Universidad del Valle de Guatemala
    Algoritmos y estructuras de datos
    Karen Tojin   08091
    Fecha: 15 de Agosto de 2009
    Descricion: Programa que crea un árbol de Huffman.
***************************************************************************** */

/**
 *
 * @author karenAndy
 */

import java.util.ArrayList;

public class HuffmanTree {
    TreeNode<String> father;
    ArrayList<TreeNode> hufTree=new ArrayList<TreeNode>();
    ArrayList<TreeNode> list = new ArrayList<TreeNode>();

    //Constructor for a new Huffman Tree
    public HuffmanTree(){
        father=new TreeNode("");
    }

    //Method that creates a new Tree from a sortedList
    public void NewTree(SortedList otherList){
        this.hufTree=otherList.getList();
        for(int i=0; i<this.hufTree.size(); i++){
            getListTemp().add(this.hufTree.get(i));
        }

        this.father.setCharacter((String)this.hufTree.get(0).getCharacter());
        this.hufTree.remove(0);

        while(hufTree.isEmpty()!=true)
        {
            TreeNode rightChild = new TreeNode("");
            TreeNode leftChild = new TreeNode(hufTree.get(0).getCharacter());

            hufTree.remove(0);

            rightChild.setLeftChild(father.getLeftChild());
            rightChild.setRightChild(father.getRightChild());
            rightChild.setCharacter(father.getCharacter());

            this.father.setLeftChild(leftChild);
            this.father.setRightChild(rightChild);
            this.father.setCharacter(father.getLeftChild().getCharacter()+""+father.getRightChild().getCharacter());
        }
    }

    //Method to find a character in the list
    public boolean findCharacter(String searchedChar, TreeNode otherNode){
        String compare=otherNode.toString();
        for(int i=0; i<compare.length();i++){
            if(compare.charAt(i)==searchedChar.charAt(0))
                return true;
        }
        return false;
    }

    //Method that returns the HuffmanTree (the string binary code)
    public String getHufTree(String character){
        TreeNode temp = new TreeNode("");
        String binaryCode="";

        temp.setLeftChild(father.getLeftChild());
        temp.setRightChild(father.getRightChild());
        temp.setCharacter(father.getCharacter());
        do{
            if(findCharacter(character,temp.getRightChild())){
                binaryCode+="1";

                TreeNode tempRight = new TreeNode("");

                tempRight.setLeftChild(temp.getLeftChild());
                tempRight.setRightChild(temp.getRightChild());
                tempRight.setCharacter(temp.getRightChild().getCharacter());

                temp.setLeftChild(tempRight.getRightChild().getLeftChild());
                temp.setRightChild(tempRight.getRightChild().getRightChild());
                temp.setCharacter(tempRight.getRightChild().getCharacter());

                if(temp.getRightChild()==null)
                    break;
            }
            else if(findCharacter(character,temp.getLeftChild())){
                binaryCode+="0";
                break;
            }
        }while(true);
        return binaryCode;
    }

    //Method the returns the current list
    public ArrayList<TreeNode> getListTemp() {
        return list;
    }
}

